In a field of distributed storage, a replication technology is widely spread in which data is duplicated so as to avoid data loss due to a disk failure or a block failure. In recent years, an erasure code technology is being actively researched and developed in which data is efficiently encoded to incorporate a minimum redundancy so as to implement further improvements in reliability and capacity efficiency.
There is a so-called Reed-Solomon (RS) code as a sort of erasure code. In a conventional redundant array of inexpensive disks (RAID) in which the RS code is adopted, a parity is calculated from all of the disks made to be redundant. Accordingly, the data and the parity used for restoring lost data are read from most of the disks in order to restore the lost data when a fault occurs.
When the number of disks from which the data and the parity used for restoration are read is increased, a processing load on read processing is increased. In the distributed storage in which a plurality of nodes equipped with disks are connected through a network, a data transfer amount between the nodes is increased. Such an increase of the processing load or the data transfer amount may cause reduction of a recovery speed.
As a technology relevant to data restoration, an n-way parity protection technique has been suggested in which restoration from a failure is enabled for up to “n” memory devices in a parity group of a storage array encoded to provide protection against an n-way disk failure.
A data restoration technology has also been suggested in which a plurality of data disks are arranged in a matrix form with n rows and m columns and the parities of redundant disks of the respective columns and the parities of redundant disks of the respective rows are used to restore data of a data disk when multiple faults occur. Further, a technology has been suggested in which data, copies of the data, and parities are distributed to be arranged in different disks on a disk array.
Related techniques are disclosed in, for example, Japanese National Publication of International Patent Application No. 2013-506191, Japanese Laid-open Patent Publication No. 2000-148409, and Japanese National Publication of International Patent Application No. 2006-505035.
In a case of RAID in which parities are calculated from all of the redundant disks, the same number of data pieces as the number of the parities may be restored. However, there is room for improvement on the recovery speed. When each of a plurality of parities is calculated using data of a portion of a plurality of data disks and the entire data is compensated using the plurality of parities, the recovery speed may be improved. However, depending on the setting of data ranges (compensation range) to be compensated by the respective parities, there is a risk that unrecoverable data is generated when multiple faults occur.
Here, the compensation refers that lost data is to be restored using the remaining data in a compensation range including the lost data and a parity associated with the compensation range. A recovery speed and reliability (reduction in the risk) are in a tradeoff relationship. As described above, in a case where each of a plurality of parities is calculated using data of a portion of disks, the improvement of reliability may be expected when the number of parities is increased, but the recovery speed may be reduced in exchange for the improvement of reliability. In other words, when it is possible to reduce the risk without increasing the number of parities, it becomes possible to improve the reliability while suppressing the reduction of recovery speed.